#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INIT    10000 
#define TOTAL   1000000

struct node {
    struct node *parent;
    struct node *lchild;
    struct node *rchild;
    double      value;
};

int add_node(struct node *parent, struct node *np)
{
    double d = np->value;

    if (parent->lchild == NULL || parent->rchild == NULL) {
        np->parent = parent;

        if (parent->lchild == NULL)
            parent->lchild = np;
        else
            parent->rchild = np;
    }
    else {
        printf("invalid parent node\n");
        return -1;
    }

    while (parent != NULL) {
        if (d < parent->value) {
            np->value = parent->value;
            parent->value = d;
            np = parent;
            parent = np->parent;
        }
        else
            break;
    }
    return 0;
}

void sift(struct node *root)
{
    struct node *np = root;
    double d = np->value;

    while (np->lchild != NULL) {
        if (np->rchild == NULL) {
            if (np->lchild->value < d) {
                np->value = np->lchild->value;
                np->lchild->value = d;
                np = np->lchild;
            }
            else
                break;
        }
        else {
            if (np->lchild->value<d && np->lchild->value<np->rchild->value) {
                np->value = np->lchild->value;
                np->lchild->value = d;
                np = np->lchild;
            }
            else if (np->rchild->value<d && np->rchild->value<np->lchild->value) {
                np->value = np->rchild->value;
                np->rchild->value = d;
                np = np->rchild;
            }
            else
                break;
        }
    }
}

void replace_node(struct node *root, double d)
{
    if (d > root->value)
        root->value = d;
    sift(root);
}

void sort_node(struct node *root, int index)
{
    while (index > 0) {
        printf("%g ", root->value);

        if ((root+index)->parent->lchild == root+index)
            (root+index)->parent->lchild = NULL;
        else
            (root+index)->parent->rchild = NULL;
        replace_node(root, (root+index)->value);
        index --;
    }
    printf("%g \n", root->value);
}

int main()
{
    int i;
    struct node nodes[INIT];

    srandom(time(NULL));
    nodes[0].value = random();
    nodes[0].lchild = NULL;
    nodes[0].rchild = NULL;
    nodes[0].parent = NULL;
    for (i = 1; i < INIT; i++) {
        nodes[i].lchild = NULL;
        nodes[i].rchild = NULL;
        nodes[i].parent = NULL;
        nodes[i].value = random();
        add_node(nodes+(i+1)/2-1, nodes+i); 
    }
    
    for (i = INIT; i < TOTAL; i++) {
        replace_node(nodes, random());
    }
    
    sort_node(nodes, INIT-1);
}

